Exponentiation (or, in the groups employing additive notation, multiplication) is one of the most time-consuming operations of many public-key cryptographic protocols. One study of the SSL/TLS protocol estimated the performance hit of the RSA (Rivest Shamir Adleman) exponentiation to be between 20% and 60% of the total server running time.
Modular exponentiation (computing gx mod N) is very common and by far the most expensive operation of many cryptographic protocols. Traditional methods for fast exponentiation transform the binary exponent either implicitly or explicitly into an addition chain, which is used directly to perform exponentiation. However, it is computationally infeasible to generate optimal addition chains for large exponents. The traditional method of raising g to a random power x is to first generate random x and then apply the best available method for computing gx. However, this approach uses the inherently suboptimal step of generating the addition chain from an exponent.
There are many approaches to speeding up exponentiation in finite groups. The most general one is to treat g and x as inputs to the exponentiation algorithm, computing gx, and optimizing the algorithm's average (or worst case) running time. A different approach, called the fixed-base method, is applicable when g is fixed and thus the algorithm can take advantage of some precomputation that would be amortized over many invocations of the exponentiation algorithm. Yet another approach is to draw the exponent from a strategically chosen set that minimizes the expected running time of the exponentiation algorithm.
In view of the foregoing, there is a need for systems and methods that overcome such deficiencies. For example, it would be desirable to reduce the running time of exponentiation without increasing any memory requirement.